package com.captjack.math;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/16 22:21
 * package com.captjack.math
 */
public class Common {

    /**
     * 最大公约数
     *
     * @param a a
     * @param b b
     * @return gcd
     */
    public long gcd(long a, long b) {
        long remainder;
        while (b > 0) {
            remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    /**
     * 最小公倍数
     *
     * @param a a
     * @param b b
     * @return lcm
     */
    public long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    /**
     * 欧拉函数
     *
     * @param n 欧拉函数
     * @return 欧拉函数
     */
    public static long eulerPhi(long n) {
        long res = n;
        long sqrt = (long) Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if (n % i == 0) {
                // 先除再乘防止溢出
                res = res / i * (i - 1);
            }
            // 每个质因数只处理一次，可以把已经找到的质因数除干净
            while (n % i == 0) {
                n /= i;
            }
        }
        if (n > 1) {
            // 最后剩下的部分也是原来的n的质因数
            res = res / n * (n - 1);
        }
        return res;
    }

    /**
     * 速降幂
     *
     * @param a     底数
     * @param power 指数
     * @param mod   mod
     * @return mod
     */
    public static long quickPower(long a, long power, long mod) {
        long res = 1;
        while (power > 0) {
            if ((power & 1) == 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            // 右移一位
            power >>= 1;
        }
        return res;
    }

    /**
     * 速降幂
     *
     * @param a     底数
     * @param power 指数
     * @param mod   mod
     * @return mod
     */
    public static int quickPower(int a, int power, int mod) {
        return (int) quickPower(a, (long) power, mod);
    }

    /**
     * 是否可以回文
     * 满足回文的条件是对所有字符的出现次数，允许且最多一个是奇数
     *
     * @param arr 各字符出现次数
     * @return 是否可以回文
     */
    public static boolean palindromeCheck(int[] arr) {
        int oddCount = 0;
        for (int data : arr) {
            if ((data & 1) == 1 && ++oddCount > 1) {
                return false;
            }
        }
        return false;
    }

}
